package org.langqiao.algorithm;
import java.math.BigInteger;
import java.util.Arrays;
public class ShuiXianHua {
	private static BigInteger[] table=new BigInteger[10];
	public static void main(String[] args)
	{
		long time=System.nanoTime();
		find(21);//调用自定义的find方法
		time=System.nanoTime()-time;
		System.out.println(time/1000000000.0+"s");
	}
    public static void find(int n)
    {
    	for(int i=0;i<10;i++)
    		table[i]=BigInteger.valueOf(i).pow(n);
    	int[] nums=new int[n];
    	int num=0;
    	int index=0;
    	BigInteger sum=BigInteger.ZERO;
    	BigInteger Min=BigInteger.TEN.pow(n-1);
    	BigInteger Max=BigInteger.TEN.pow(n).subtract(BigInteger.ONE);
    	while(true)
    	{
    		if(index<nums.length&&num<10)
    		{
    			BigInteger temp=sum.add(table[num]);
    			if(temp.compareTo(Max)<0)
    			{
    				nums[index]=num;
    			    index++;
    			    sum=temp;
    			    continue;
    			}
    		}
    		else if(index>=nums.length&&sum.compareTo(Min)>0)
    		{
    			int[] temp=getArray(sum);//调用自定义的getArray()方法
    			if(check(nums,true,temp,false))//调用自定义的check方法
    			{
    				System.out.println(sum);
    				
    			}
    			else if(index<=0)
    			{
    				
    					break;
    			}
    			index--;
    			num=nums[index];
    			sum=sum.subtract(table[num]);
    			num++;
    		}
    		
    	}
    }
    	public static boolean check(int[] a1,boolean copy1,int[] a2,boolean copy2)
    	{
    		if(a1.length!=a2.length)
    			return false;
    		if(copy1)
    			a1=a1.clone();
    		if(copy2)
    			a2=a2.clone();
    		Arrays.sort(a1);
    		Arrays.sort(a2);
    		return Arrays.equals(a1,a2);
    	}
    	public static int[] getArray(BigInteger big)
    	{
    		String s=String.valueOf(big);
    		int length=s.length();
    		int[] res=new int[length];
    		for(int i=0;i<length;i++)
    		{
    			res[i]=s.charAt(i)-'0';
    		}
    		return res;    		
    	}
}
